package com.zm.demo.core.sort;

import java.util.Arrays;
import java.util.Random;

import static java.lang.System.out;

/**
 * @author zoum
 * @create 2020/3/10 13:17
 */
public class QuickSort1 {

    private static Random random = new Random();

    public static void main(String[] args){
        int[]a = {0, 1,2,4,5,7,8,4,3,6,2,3,4,5,9,8,7,1,0};
        quickSort(a, 0, a.length-1);
    }

    public static void quickSort(int[]a, int start,int end) {
        if (start>=end){
            return;
        }
        int p = partition1(a, start, end);
        out.println(Arrays.toString(a));
        quickSort(a, start,p-1);
        quickSort(a, p+1, end);
    }

    /**
     * 3,5,4,1,2  p=0
     * 3,5,4,1,2  p=0
     * 3,5,4,1,2  p=0
     * 1,3,5,4,2  p=1
     * 1,2,3,5,4  p=2
     * 借鉴插入排序的思想
     */
    private static int partition(int[] a, int start, int end) {
        int p = start;
        for (int i = start+1; i <= end ; i++) {
            if (a[i] < a[p]){
                int tmp = a[i];
                for (int j = i; j > p; j--) {
                    a[j] = a[j-1];
                }
                a[p] = tmp;
                p++;
            }
        }
        return p;

    }
    /**
     * 3,5,4,1,2  p=0 base=3
     * 3,5,4,1,2  p=0 base=3
     * 3,5,4,1,2  p=0 base=3
     * 1,5,4,3,2  p=1 base=3
     * 1,2,4,3,5  p=2 base=3
     * 1,2,3,4,5  p=2 base=3
     *
     */
    private static int partition1(int[] a, int start, int end) {
        int p = start;//初始分界线
        int base = a[start];//基准值
        for (int i = start; i <= end ; i++) {
            if (a[i] < base){
                swap(a,i,p);
                p++;
            }

        }
        return p;

    }

    private static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}
